﻿#define _CRT_SECURE_NO_WARNINGS 1
#pragma warning(disable : 6031)
#include "heap.h"

void hpinit(hp* head)
{
	assert(head);
	head->p = NULL;
	head->num = 0;
	head->size = 0;
}

void hpdestroy(hp* head)
{
	assert(head);
	free(head->p);
	head->size = 0;
	head->num = 0;
}

void swap(datatype* pa, datatype* pb)
{
	datatype tmp = *pa;
	*pa = *pb;
	*pb = tmp;
}

void hpjump(datatype* p, int child)
{
	datatype parent = (child - 1) / 2;
	while (child > 0)
	{
		if (p[child] < p[parent])
		{
			swap(&p[child], &p[parent]);

			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

void hpdown(datatype* p, int size, int parent)
{
	int child = parent * 2 + 1;

	while (child < size)
	{
		if (child + 1 < size && p[child] > p[child + 1])
		{
			child++;
		}
		if (p[child] < p[parent])
		{
			swap(&p[child], &p[parent]);

			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

void hppush(hp* head, datatype x)
{
	if (head->size == head->num)
	{
		int newnum = head->num == 0 ? 4 : head->num * 2;
		datatype* newp = (datatype*)realloc(head->p, sizeof(datatype)*newnum);
		if (!newp)
		{
			perror("malloc");
			return;
		}
		head->p = newp;
		head->num = newnum;
	}
	head->p[head->size] = x;
	head->size++;
	hpjump(head->p, head->size-1);
}

void hppop(hp* head)
{
	assert(head);
	assert(!hpempty(head));

	swap(&head->p[0], &head->p[head->size - 1]);
	head->size--;

	hpdown(head->p, head->size, 0);
}

bool hpempty(hp* head)
{
	return head->size == 0;
}

datatype hptop(hp* head)
{
	assert(head);
	assert(!hpempty(head));
	
	return head->p[0];
}


int hpsize(hp* head)
{
	assert(head);
	return head->size;
}